/*
 * @lc app=leetcode.cn id=427 lang=cpp
 *
 * [427] 建立四叉树
 */

// @lc code=start
/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution
{
public:
    int isAllSame(vector<vector<int>> &grid, int r0, int r1, int c0, int c1)
    {
        for (int i = r0; i < r1; i++)
        {
            for (int j = c0; j < c1; j++)
            {
                if (grid[r0][c0] != grid[i][j])
                {
                    return 0;
                }
            }
        }
        return 1;
    }
    Node *dfs(vector<vector<int>> &grid, int r0, int r1, int c0, int c1)
    {
        int allSame = isAllSame(grid, r0, r1, c0, c1);
        if (allSame)
        {
            return new Node(grid[r0][c0], true);
        }
        Node *root = new Node(
            false,
            false,
            dfs(grid, r0, (r0 + r1) >> 1, c0, (c0 + c1) >> 1),
            dfs(grid, r0, (r0 + r1) >> 1, (c0 + c1) >> 1, c1),
            dfs(grid, (r0 + r1) >> 1, r1, c0, (c0 + c1) >> 1),
            dfs(grid, (r0 + r1) >> 1, r1, (c0 + c1) >> 1, c1));

        return root;
    }
    Node *construct(vector<vector<int>> &grid)
    {
        int n = grid.size();
        return dfs(grid, 0, n, 0, n);
    }
};
// @lc code=end
